package ee.project.redblacktree;

public class RBTree {

	private RBNode root;
	private RBNode nullNode;

	private final static int BLACK = 0;
	private final static int RED = 1;

	public RBTree() {
		nullNode = new RBNode(null);
		nullNode.color = BLACK;
		root = nullNode;
	}

	private void leftRotate(RBNode x) {
		RBNode y = x.right;
		x.right = y.left;
		if (y.left != nullNode) {
			y.left.parent = x;
		}
		y.parent = x.parent;
		if (x.parent == nullNode) {
			root = y;
		} else if (x == x.parent.left) {
			x.parent.left = y;
		} else {
			x.parent.right = y;
		}
		y.left = x;
		x.parent = y;
	}

	private void rightRotate(RBNode y) {
		RBNode x = y.left;
		y.left = x.right;
		if (x.right != nullNode) {
			x.right.parent = y;
		}
		x.parent = y.parent;
		if (y.parent == nullNode) {
			root = x;
		} else if (y == y.parent.left) {
			y.parent.left = x;
		} else {
			y.parent.right = x;
		}
		x.right = y;
		y.parent = x;
	}

	private void insert(RBNode node) {
		RBNode y = nullNode;
		RBNode x = root;
		while (x != nullNode) {
			y = x;
			if (node.key.compareTo(x.key) < 0) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		node.parent = y;
		if (y == nullNode) {
			root = node;
		} else if (node.key.compareTo(y.key) < 0) {
			y.left = node;
		} else {
			y.right = node;
		}
		node.left = nullNode;
		node.right = nullNode;
		node.color = RED;
		insertFixUp(node);
	}

	private void insertFixUp(RBNode node) {
		while (node.parent.color == RED) {
			if(node.parent == node.parent.parent.left){
				
			}
		}
	}
}
